#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>


typedef struct Qnode
{
	int data;
	struct Qnode* next;
}Qnode,*QueuePtr;

typedef struct
{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;

void Init_Queue(LinkQueue &Q)
{
	Q.front = Q.rear = (QueuePtr)malloc(sizeof(Qnode));
	if (!Q.front)
		printf("内存空间创建失败!\n");
	else
		Q.front->next = NULL;
}


void Destroy_Queue(LinkQueue& Q)
{
	if (!Q.front)
		printf("该队列不存在!\n");
	else
	{
		while (Q.front)
		{
			QueuePtr p = Q.front->next;//Q.rear=Q.front->next;
			free(Q.front);//free(Q.front);
			Q.front = p;//Q.front=Q.rear;
		}//节省空间
		printf("销毁队列成功!\n");
	}
}


void Entry_Queue(LinkQueue& Q,int e)
{
	if (!Q.front)
		printf("该队列不存在!\n");
	else
	{
		QueuePtr p = (QueuePtr)malloc(sizeof(Qnode));
		if (!p)
			printf("内存分配失败!\n");
		else
		{
			p->data = e;
			p->next = NULL;
			Q.rear->next = p;
			Q.rear = p;
		}	
	}
}

void Out_Queue(LinkQueue& Q)
{
	if (!Q.front)
		printf("该队列不存在!\n");
	else
	{
		if (Q.front==Q.rear)
			printf("该队列为空\n");
		else
		{
			QueuePtr p = Q.front->next;
			printf("出队元素为:%d\n", p->data);
			Q.front->next = p->next;
			if (Q.rear == p)
				Q.rear = Q.front;
			free(p);
		}
	}
}

void Get_Head(LinkQueue& Q)
{
	if (!Q.front)
		printf("该队列不存在!\n");
	else
	{
		if (Q.front == Q.rear)
			printf("该队列为空\n");
		else
			printf("队头元素为:%d\n", Q.front->next->data);
	}
}

void Traverse_Queue(LinkQueue& Q)
{
	if (!Q.front)
		printf("该队列不存在!\n");
	else
	{
		if (Q.front == Q.rear)
			printf("该队列为空\n");
		else
		{
			QueuePtr p = Q.front->next;
			while (p)
			{
				printf("%d ", p->data);
				p = p->next;
			}
			printf("\n");
		}
	}
}


int main()
{
	LinkQueue Q = { Q.front = NULL,Q.rear = NULL };
	printf("     链式队列    \n");
	printf("0.退出操作.\n");
	printf("1.初始化链式队列.\n");
	printf("2.销毁队列.\n");
	printf("3.入队.\n");
	printf("4.出队.\n");
	printf("5.取队头元素.\n");
	printf("6.遍历队列.\n");
	while (1)
	{
		int n = 0;
		int x = 0;
		int e = 0;
		printf("请选择对应操作:");
		scanf("%d", &n);
		switch (n)
		{
		case 0:
			x = 1;
			break;
		case 1:
			Init_Queue(Q);
			break;
		case 2:
			Destroy_Queue(Q);
			break;
		case 3:
			printf("请输入入队元素:");
			scanf("%d", &e);
			Entry_Queue(Q,e);
			break;
		case 4:
			Out_Queue(Q);
			break;
		case 5:
			Get_Head(Q);
			break;
		case 6:
			Traverse_Queue(Q);
			break;
		}
		if (x == 1)
			break;
	}
}